#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef struct Stack {
	int* data;
	int top;
	int capacity;
}ST;

void STInit(ST* ps) {
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STDestroy(ST* ps) {
	ps->data = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
void STPush(ST* ps, int x) {
	if (ps->top == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* tmp = (int*)realloc(ps->data,sizeof(int) * newcapacity);
		if (tmp == NULL) {
			perror("realloc failed");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->top = x;
	ps->top++;
}

void STPop(ST* ps) {
	ps->top--;
}
int STTop(ST* ps) {
	return ps->data[ps->top - 1];
}
int STEmpty(ST* ps) {
	if (ps->top == 0) {
		return 1;
	}
	return 0;
}

